package main

import "fmt"

//用时54%，内存80%
func maxAreaOfIsland(grid [][]int) int {
	num := []int{}
	var area int
	var tmp int

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				tmp += area
				area = 0
				dfs(grid, i, j)
				for i := 0; i < len(grid); i++ {
					for j := 0; j < len(grid[0]); j++ {
						if grid[i][j] == 2 {
							area += 2
						}
					}
				}
				area -= tmp
				num = append(num, area/2)

			}
		}
	}
	if len(num) == 0 {
		return 0
	} else if len(num) == 1 {
		return num[0]
	}
	for i := 1; i < len(num); i++ {
		if num[0] < num[i] {
			num[0], num[i] = num[i], num[0]
		}
	}
	return num[0]
}

func isArea(grid [][]int, r, c int) bool {
	return r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0])
}

func dfs(grid [][]int, r, c int) {
	if !isArea(grid, r, c) {
		return
	}
	if grid[r][c] != 1 {
		return
	} else {
		grid[r][c] = 2
	}
	dfs(grid, r+1, c)
	dfs(grid, r-1, c)
	dfs(grid, r, c+1)
	dfs(grid, r, c-1)
}

//指针传递面积，用时93%，内存76%
func maxAreaOfIsland1(grid [][]int) int {
	var area int
	var maxarea int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				area = 0
				dfs1(grid, i, j, &area)
				if area > maxarea {
					maxarea = area
				}
			}
		}
	}
	return maxarea
}

func dfs1(grid [][]int, r, c int, area *int) {
	if !isArea(grid, r, c) {
		return
	}
	if grid[r][c] != 1 {
		return
	} else {
		grid[r][c] = 2
		*area++
	}
	dfs1(grid, r+1, c, area)
	dfs1(grid, r-1, c, area)
	dfs1(grid, r, c+1, area)
	dfs1(grid, r, c-1, area)
}

func main() {
	grid1 := [][]int{{0, 1, 1}, {0, 1, 1}}
	grid := [][]int{{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
		{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
		{0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}}
	fmt.Println(maxAreaOfIsland(grid1))
	fmt.Println(maxAreaOfIsland1(grid))
}
